package com.company.笔试.重构二叉树; /**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import com.company.笔试.TreeNode;

import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        if(pre.length<=0||vin.length<=0) return null;
        TreeNode res = new TreeNode(pre[0]);//前序第一个节点是根节点
        if(pre.length==1||vin.length==1) return res;//只有一个节点返回
        for(int i =0 ;i<vin.length;i++){
            if(pre[0] == vin[i]){ //1.找到根节点在中序位置i
                //2.重构左子树    Arrays.copyOfRange左闭右开
                //3. i是前序左子树的长度  , 也是中序根所在的索引  把左子树递归,左子树的前序pre[1,i+1]  中序vin[0,i]
                TreeNode left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                //4 重构右子树  把右子树递归,右子树的前序pre[i+1,pre.length]  中序vin[i+1,vin.length]
                TreeNode right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
                //根节点重构左右子树
                res.left = left;
                res.right = right;
                break;
            }
        }
        
        return res;
        
    }
}